package com.c2b.algorithm.leetcode.base.unionfind;

/**
 * @author c2b
 * @since 2024/3/5 11:23
 */
public class LC0684 {
    static class Solution {
        public int[] findRedundantConnection(int[][] edges) {
            int edgeCount = edges.length;
            int[] parent = new int[edgeCount];
            for (int i = 1; i <= edgeCount; i++) {
                parent[i] = i;
            }
            for (int[] edge : edges) {

                int node0 = edge[0];
                int node1 = edge[1];
                // 两个集合代表节点相同，说明出现环，返回答案
                if (find(parent, node0) != find(parent, node1)) {
                    return edge;
                }
                // 两个集合独立，合并集合。将前一个集合代表节点戳到后一个集合代表节点上
                union(parent, node0, node1);
            }
            return new int[0];
        }

        private void union(int[] parent, int x, int y) {
            parent[find(parent, x)] = find(parent, y);
        }

        private int find(int[] parent, int x) {
            if (parent[x] != x) {
                parent[x] = find(parent, parent[x]);
            }
            return parent[x];
        }
    }
}
